Propagation down the dual segment tree

How should the "overwrite value" range action be defined?

The range action doesn't know which is later, whether the node is above or below.

So I made the value timestamped, and propagation downwards is a binary operation that "takes the one with the newer timestamp".

This again implies the following

The implementation unintentionally assumed that the action was commutative.

Incorrect operation in case of non commutative "overwrite action

Converted to a commutative max operation by adding a timestamp.

Half-delayed segment tree] omits the value segment tree when only a point acquisition is needed.

I correctly constructed a dual segment tree, but overlooked the "action composition is commutative".

Demo with two range actions and f and g overlapping out of order.

If the propagation downwards is commutative, it doesn't matter if the order is switched here.

code:python

>> range_update(table, 3, 10, lambda x: "f")

>> range_update(table, 5, 15, lambda x: "g")

>> debugprint(table)

| 0 |

| 0 | 0 |

| 0 | f | g | 0 |

| 0 | 0 | 0 | g | f | 0 | g | 0 |

|0|0|0|f|0|g|0|0|0|0|0|0|0|0|g|0|

The right way to do it when it is not commutative

Propagate down before the second range action.

It is guaranteed that the cell above the cell to be rewritten in the next range action is down.

code:python

>> range_update(table, 3, 10, lambda x: "f")

>> down_propagate(table, up(5), lambda x, y: x if x else y, 0)

>> down_propagate(table, up(15), lambda x, y: x if x else y, 0)

>> debugprint(table)

| 0 |

| 0 | 0 |

| 0 | 0 | 0 | 0 |

| 0 | 0 | 0 | f | f | 0 | 0 | 0 |

|0|0|0|f|f|f|0|0|0|0|0|0|0|0|0|0|

>> range_update(table, 5, 15, lambda x: "g")

>> debugprint(table)

| 0 |

| 0 | 0 |

| 0 | 0 | g | 0 |

| 0 | 0 | 0 | g | f | 0 | g | 0 |

|0|0|0|f|f|g|0|0|0|0|0|0|0|0|g|0|

---